
/**
 * https://leetcode-cn.com/problems/binary-tree-preorder-traversal/
 * 二叉搜索树的前序遍历
 * @param root 
 */
const preorderTraversal = (root: TreeNode | null): number[] => {
    // 树为空
    if (root === null) return []

    const arr: number[] = []

    // 模拟栈
    const stack: TreeNode[] = [root]

    while (stack.length > 0) {
        let n: TreeNode | null = stack.pop()!

        while (n !== null) {
            // 访问节点    
            arr.push(n.val)
            // 放入栈中
            if (n.right !== null) stack.push(n.right);

            // 遍历左子树 
            n = n.left;
        }
    }


    return arr
};


const preorderTraversal3 = (root: TreeNode | null): number[] => {
    const arr: number[] = []

    /**
     * 获取前驱节点
     * @param n 
     */
    const getAced = (n: TreeNode) => {
        let left = n.left;

        // 一直往左子树的右边找
        while (left !== null && left.right !== null) {
            left = left.right;
        }

        return left;
    }

    while (root !== null) {
        if (root.left !== null) {
            // 访问节点
            arr.push(root.val);

            // 找到前驱节点, 让前驱节点的right指向当前节点的右节点
            const aced = getAced(root)!;

            // 为空, 让其right指向当前节点
            if (aced.right == null) {
                aced.right = root.right;
                root = root.left;
            }
        } else {
            // 访问节点
            arr.push(root.val)

            // 左子树为空
            root = root.right!;
        }
    }
    return arr
};

// 递归
const preorderTraversal2 = (root: TreeNode | null): number[] => {
    const arr: number[] = []

    const preOrder = (n: TreeNode | null) => {
        if (n === null) return;
        arr.push(n.val);
        // 左边
        preOrder(n.left)
        // 右边
        preOrder(n.right)
    }

    preOrder(root);

    return arr;
};